package class15;

import class14.Code05_UnionFind;

/**
 * <a href="https://leetcode.cn/problems/number-of-islands/">200. 岛屿数量</a>
 * <a href="https://leetcode.cn/problems/max-area-of-island/">695. 岛屿的最大面积</a>
 */
public class Code02_NumberOfIslands {

    // DFS
    public int numIslands1(char[][] grid) {
        int result = 0;
        for (int row = 0; row < grid.length; ++row) {
            for (int col = 0; col < grid[row].length; ++col) {
                if (grid[row][col] != '1') {
                    continue;
                }
                process(grid, row, col);
                result++;
            }
        }
        return result;
    }

    private void process(char[][] grid, int row, int col) {
        if (row < 0 || row == grid.length || col < 0 || col == grid[row].length || grid[row][col] != '1') {
            return;
        }
        grid[row][col] = '2';
        process(grid, row - 1, col);
        process(grid, row + 1, col);
        process(grid, row, col - 1);
        process(grid, row, col + 1);
    }

    // 并查集
    public int numIslands2(char[][] grid) {
        UnionFind unionFind = new UnionFind(grid);
        for (int row = 1; row < grid.length; ++row) {
            if (grid[row - 1][0] == '1' && grid[row][0] == '1') {
                unionFind.union(row - 1, 0, row, 0);
            }
        }
        for (int col = 1; col < grid[0].length; ++col) {
            if (grid[0][col - 1] == '1' && grid[0][col] == '1') {
                unionFind.union(0, col - 1, 0, col);
            }
        }
        for (int row = 1; row < grid.length; ++row) {
            for (int col = 1; col < grid[row].length; ++col) {
                if (grid[row][col] != '1') {
                    continue;
                }
                if (grid[row - 1][col] == '1' && grid[row][col] == '1') {
                    unionFind.union(row - 1, col, row, col);
                }
                if (grid[row][col - 1] == '1' && grid[row][col] == '1') {
                    unionFind.union(row, col - 1, row, col);
                }
            }
        }
        return unionFind.sets;
    }

    private static class UnionFind {
        int row, col;
        int[] parent;
        int[] size;
        int[] stack;
        int sets;

        UnionFind(char[][] grid) {
            row = grid.length;
            col = grid[0].length;
            sets = 0;
            int n = row * col;
            parent = new int[n];
            size = new int[n];
            stack = new int[n];
            for (int r = 0; r < row; ++r) {
                for (int c = 0; c < col; ++c) {
                    if (grid[r][c] != '1') {
                        continue;
                    }
                    int i = index(r, c);
                    parent[i] = i;
                    size[i] = 1;
                    sets++;
                }
            }
        }

        int index(int r, int c) {
            return r * col + c;
        }

        int find(int i) {
            int si = 0;
            // 找到头结点
            while (i != parent[i]) {
                stack[si++] = i;
                i = parent[i];
            }
            // 将所有子结点指向头结点
            for (si--; si >= 0; si--) {
                parent[stack[si]] = i;
            }
            return i;
        }

        void union(int row1, int col1, int row2, int col2) {
            int head1 = find(index(row1, col1));
            int head2 = find(index(row2, col2));
            if (head1 == head2) {
                return;
            }
            if (size[head1] > size[head2]) {
                size[head1] += size[head2];
                parent[head2] = head1;
            } else {
                size[head2] += size[head1];
                parent[head1] = head2;
            }
            sets--;
        }
    }

}
